#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

//string decodeString(string s) {
//    vector<int> nums;
//    vector<string> str;
//
//    for (int i = 0; i < s.size(); )
//    {
//        char ch = s[i];
//        if (ch > '0' && ch <= '9')
//        {
//            int tmp = 0;
//            while (s[i] > '0' && s[i] <= '9')
//                tmp = tmp * 10 + (s[i++] - '0');
//            nums.push_back(tmp);
//        }
//        else if (ch == '[')
//        {
//            i++;
//            string tmp;
//            while (s[i] >= 'a' && s[i] <= 'z')
//                tmp += s[i++];
//            str.push_back(tmp);
//        }
//        else if (ch == ']')
//        {
//            int n = nums.back();
//            nums.pop_back();
//            string m = str.back();
//            str.pop_back();
//            string tmp;
//            while (n-- > 0)
//                tmp += m;
//            if (str.size())
//                str.back() += tmp;
//            else
//                str.push_back(tmp);
//        }
//        else
//        {
//            string tmp;
//            while (s[i] >= 'a' && s[i] <= 'z')
//                tmp += s[i++];
//            str.back() += tmp;
//        }
//    }
//    return str[0];
//}
//
//int main()
//{
//    decodeString("3[a]2[bc]");
//    return 0;
//}

//bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
//    vector<int> stack;
//    int cur1 = 0, cur2 = 0, n1 = pushed.size(), n2 = popped.size();
//
//    while (cur2 < n2)
//    {
//        if (cur1 < n1)
//        {
//            stack.push_back(pushed[cur1++]);
//            while (cur2 < n1 && stack.back() == popped[cur2])
//            {
//                stack.pop_back();
//                cur2++;
//            }
//        }
//        else
//        {
//            if (stack.back() == popped[cur2])
//            {
//                stack.pop_back();
//                cur2++;
//            }
//            else
//                return false;
//        }
//    }
//    return true;
//}
//
//int main()
//{
//    vector<int> push = { 1,0 }, pop = { 1, 0 };
//
//    bool ret = validateStackSequences(push, pop);
//    cout << ret << endl;
//    return 0;
//}

//struct TreeNode {
//    int val;
//    TreeNode* left;
//    TreeNode* right;
//    TreeNode() : val(0), left(nullptr), right(nullptr) {}
//    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
//    
//};
//
//vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
//    vector<vector<int>> ret;
//    if (root == nullptr)
//        return ret;
//
//    queue<TreeNode*> q;
//    q.push(root);
//    int n = 1;
//    while (q.size())
//    {
//        int sz = q.size();
//        vector<int> tmp;
//        for (int i = 0; i < sz; i++)
//        {
//            TreeNode* t = q.front();
//            q.pop();
//            tmp.push_back(t->val);
//
//            if (t->left != nullptr)
//                q.push(t->left);
//            if (t->right != nullptr)
//                q.push(t->right);
//        }
//        if (n / 2 == 0)
//            reverse(tmp.begin(), tmp.end());
//        ret.push_back(tmp);
//        n++;
//    }
//    return ret;
//}
//
//int main()
//{
//
//    return 0;
//}